class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return
        pre = None
        cur = head
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            if not temp: break
            cur = temp
        return cur

    def reverseList1(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return
        if not head.next: return head
        newhead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newhead

a1 = ListNode(1)
a2 = ListNode(2)
a3 = ListNode(3)
a4 = ListNode(4)
a5 = ListNode(5)

a4.next = a5
a3.next = a4
a2.next = a3
a1.next = a2
s=Solution()
print(s.reverseList1(a1))